1. Field of the Invention
The present invention relates to systems and techniques for manipulating digital images. More specifically, the present invention relates to a method and an apparatus for applying a filter to an image whose pixel values can span a large range of values.
2. Related Art
One of the problems in displaying a “real world” scene is that the dynamic range of color intensity values which are present in the “real world” scene often greatly exceeds the dynamic range of display mediums which are typically used to display the scene. A technique called HDR (High Dynamic Range) tone mapping is typically used to solve this problem. HDR tone mapping techniques can be used for reducing the dynamic range of such “real world” scenes so that they can be effectively displayed on media, such as hard-copy prints, CRT/LCD displays, and projectors. These techniques usually attempt to reduce the contrast of a natural scene so that it can be displayed on a specific display medium, while preserving image details which are critical to appreciate the original scene content.
One of the techniques for HDR tone mapping involves applying a “bilateral filter” to an image. A bilateral filter is a filter that computes a new value of a pixel in the image based on the spatial closeness as well as the photometric similarity of other pixels in the image. In other words, a bilateral filter may compute a new pixel value based on the values of neighboring pixels (spatial closeness) which have values that are similar (photometric similarity) to the original pixel.
Unfortunately, prior art techniques for applying a bilateral filter to an image can require a large amount of computation. Prior art techniques typically use an approximation to a Gaussian function as the spatial component of the bilateral filter. Hence, to update a given pixel these techniques need to compute the individual contributions of each neighboring pixel during the bilateral computation. Because the range of interest is a two-dimensional area, these techniques typically require O(n2) operations for each pixel, where n is the radius (in number of pixels) of the filter. (Big “O” notation, e.g., O(n2), is commonly used to describe the asymptotic time and/or space complexity of software processes.) This is why prior art techniques can be very slow, especially when the filter radius is large.
These performance problems are not limited to bilateral filters. For example, prior art techniques for applying a trilateral filter to an image also suffer from similar performance problems. (A trilateral filter computes a new pixel value based on the spatial closeness, photometric similarity, and the gradients of neighboring pixel values.)
A system to speed up bilateral (or trilateral) filtering using histogram based techniques was described in U.S. patent application Ser. No. 11/292,184, entitled, “FAST BILATERAL FILTERING USING RECTANGULAR REGIONS” (hereinafter “Cox”). However, histogram based techniques typically speed up the filtering operation when the input data set (e.g., pixel values) spans a relatively small range of integral values. Hence, the invention of Cox may not substantially speed up bilateral filtering when the input data set spans a large range of integral or floating point values.
Hence, what is needed is a method and an apparatus for applying a filter to an input data set (e.g., pixel values) which can span a large range of integral or floating point values without the above-described performance problems.